package com.yanceysong.codetop.s61_s70;

import com.yanceysong.common.TreeNode;


public class S61_Mid_129_求根到叶子节点数字之和 {

    /**
     * 求根到叶子节点数字之和 (Sum Root to Leaf Numbers)
     * .<a href="https://leetcode.cn/problems/sum-root-to-leaf-numbers/">LeetCode题目链接</a>
     * .<p>
     * .题目要求：
     * .给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
     * .每条从根节点到叶节点的路径都可以生成一个数字：将路径上所有节点的值从根到叶依次拼接。请计算所有路径对应的数字之和。
     * .叶子节点：没有左右子节点的节点。
     * .<p>
     * .示例：
     * .1) root = [1,2,3]
     * .       1
     * .      / \
     * .     2   3    路径: 1->2 = 12, 1->3 = 13 结果=25
     * .2) root = [4,9,0,5,1]
     * .          4
     * .        /   \
     * .       9     0
     * .     /  \
     * .    5    1  路径: 4->9->5=495, 4->9->1=491, 4->0=40 总和=1026
     * .3) root = [] 输出 0
     * .<p>
     * .核心标签：二叉树 / DFS 深度优先遍历 / 回溯思想 / 递归 / 栈迭代 / 数字前缀构造
     * .<p>
     * .解题思路总览：
     * .1. 递归 DFS：传入参数为到当前节点父节点形成的十?进制数 pathPrefixValue；当前节点的完整路径数为 pathPrefixValue * .10 + node.val。
     * .   如果当前是叶子节点，直接返回该路径数字；否则递归左右子树并求和。
     * .2. 迭代 DFS：使用栈模拟递归，元素保存 (节点, 根到该节点形成的路径数)。弹出时若是叶子则累加。
     * .3. 不需要回溯清除：因为路径值采用整数传值，每层栈帧/栈元素是独立副本。
     * .<p>
     * .为什么使用 "prefix * .10 + 当前值" 可行？这是十进制数拼接的标准方式；相当于把之前的位整体左移一位（乘以10）再加上新的一位。
     * .<p>
     * .ASCII 图解 (示例2)：
     * .         4 (prefix=0 -> 4)
     * .       /   \
     * .  9 (prefix=4 -> 49)  0 (prefix=4 -> 40)  <-- 叶子 40
     * .    /        \
     * .5(495)     1(491)                         <-- 叶子 495, 491
     * .路径和: 495 + 491 + 40 = 1026
     * .<p>
     * .关键洞察 & 易错点：
     * .- 只有叶子节点时才将路径数加入结果；内部节点不能提前累加。
     * .- 空树返回 0。
     * .- 不需要使用 StringBuilder 或数组，整数运算即可，高效且简洁。
     * .- 注意不要遗漏单路径（链状）情况下的正确性，例如 1->2->3->4 => 1234。
     * .- 判定叶子条件：node.left == null && node.right == null。
     * .- 迭代实现中注意压栈顺序不影响结果，仅改变遍历次序。
     * .<p>
     * .时间复杂度：O(N)，N 为节点数，所有节点恰好访问一次。
     * .空间复杂度：递归 O(H) 调用栈；迭代 O(H) 辅助栈，H 为树高（最坏链状 O(N)）。
     * .<p>
     * .可扩展：可在遍历中收集每条路径数字列表用于调试或展示；可改写为 Morris 遍历（较复杂，不推荐初学者）。
     */
    public int sumNumbers(TreeNode root) {
        return dfsBuildAndAccumulate(root, 0);
    }

    /**
     * .递归 DFS：构造路径数字并汇总该子树所有叶子路径的数值。
     * .@param node 当前节点
     * .@param pathPrefixValue 根到当前节点父节点形成的十进制前缀数
     * .@return 从当前节点作为起点的所有根到叶子路径数字之和
     */
    private int dfsBuildAndAccumulate(TreeNode node, int pathPrefixValue) {
        if (node == null) {
            return 0; // 空节点不贡献路径
        }
        // 当前路径形成的新数字：前缀左移一位(×10) + 当前节点值
        int currentPathNumber = pathPrefixValue * 10 + node.val;

        // 叶子：完成一条路径，直接返回该数字
        if (node.left == null && node.right == null) {
            return currentPathNumber;
        }
        // 非叶子：递归左右子树（不存在的分支返回0）
        int leftSum = dfsBuildAndAccumulate(node.left, currentPathNumber);
        int rightSum = dfsBuildAndAccumulate(node.right, currentPathNumber);
        return leftSum + rightSum;
    }

    /**
     * .迭代 DFS：使用栈保存 (节点, 根到该节点形成的路径数)，模拟递归过程。
     * .@param root 根节点
     * .@return 所有路径数字之和
     */
    public int sumNumbersIterative(TreeNode root) {
        if (root == null) {
            return 0;
        }
        java.util.Deque<java.util.AbstractMap.SimpleEntry<TreeNode, Integer>> stack = new java.util.ArrayDeque<>();
        stack.push(new java.util.AbstractMap.SimpleEntry<>(root, root.val));
        int totalSum = 0;
        while (!stack.isEmpty()) {
            java.util.AbstractMap.SimpleEntry<TreeNode, Integer> state = stack.pop();
            TreeNode curr = state.getKey();
            int pathValue = state.getValue();
            if (curr.left == null && curr.right == null) {
                totalSum += pathValue; // 叶子累加
                continue;
            }
            // 压入右子树
            if (curr.right != null) {
                stack.push(new java.util.AbstractMap.SimpleEntry<>(curr.right, pathValue * 10 + curr.right.val));
            }
            // 压入左子树
            if (curr.left != null) {
                stack.push(new java.util.AbstractMap.SimpleEntry<>(curr.left, pathValue * 10 + curr.left.val));
            }
        }
        return totalSum;
    }

    // ===================== 测试代码区域 =====================
    public static void main(String[] args) {
        S61_Mid_129_求根到叶子节点数字之和 solution = new S61_Mid_129_求根到叶子节点数字之和();
        System.out.println("=== 求根到叶子节点数字之和 测试开始 ===\n");

        // 基本示例 & 边界用例
        testExample1(solution);      // 示例1
        testExample2(solution);      // 示例2
        testEmptyTree(solution);     // 空树
        testSingleNode(solution);    // 单节点
        testLeftSkewed(solution);    // 全左链
        testRightSkewed(solution);   // 全右链
        testTreeWithZero(solution);  // 含 0 节点
        testConsistencyRecursiveIterative(solution); // 两实现一致性
        testCompleteBinaryTree(solution);            // 完全二叉树
        testLargerTree(solution);    // 较大自定义
        testRandomSmallTrees(solution); // 随机生成若干小规模树对比递归与迭代

        System.out.println("\n=== 所有测试完成 ===");
    }

    // 示例1
    private static void testExample1(S61_Mid_129_求根到叶子节点数字之和 solution) {
        TreeNode root = new TreeNode(1, new TreeNode(2), new TreeNode(3));
        int ans = solution.sumNumbers(root);
        System.out.println("测试1: [1,2,3] 期望:25 实际:" + ans);
        assert ans == 25 : "示例1失败";
        System.out.println("路径: 12,13 -> 总和25 ✓\n");
    }

    // 示例2
    private static void testExample2(S61_Mid_129_求根到叶子节点数字之和 solution) {
        TreeNode root = new TreeNode(4,
                new TreeNode(9, new TreeNode(5), new TreeNode(1)),
                new TreeNode(0));
        int ans = solution.sumNumbers(root);
        System.out.println("测试2: [4,9,0,5,1] 期望:1026 实际:" + ans);
        assert ans == 1026 : "示例2失败";
        System.out.println("路径: 495,491,40 -> 总和1026 ✓\n");
    }

    // 空树
    private static void testEmptyTree(S61_Mid_129_求根到叶子节点数字之和 solution) {
        int ans = solution.sumNumbers(null);
        System.out.println("测试3: 空树 期望:0 实际:" + ans);
        assert ans == 0 : "空树应返回0";
        System.out.println("✓\n");
    }

    // 单节点
    private static void testSingleNode(S61_Mid_129_求根到叶子节点数字之和 solution) {
        TreeNode root = new TreeNode(7);
        int ans = solution.sumNumbers(root);
        System.out.println("测试4: 单节点[7] 期望:7 实际:" + ans);
        assert ans == 7 : "单节点路径数错误";
        System.out.println("路径: 7 -> 总和7 ✓\n");
    }

    // 左链
    private static void testLeftSkewed(S61_Mid_129_求根到叶子节点数字之和 solution) {
        TreeNode root = new TreeNode(1,
                new TreeNode(2,
                        new TreeNode(3,
                                new TreeNode(4), null), null), null);
        int ans = solution.sumNumbers(root);
        System.out.println("测试5: 左链[1->2->3->4] 期望:1234 实际:" + ans);
        assert ans == 1234 : "左链路径数错误";
        System.out.println("路径: 1234 -> 总和1234 ✓\n");
    }

    // 右链
    private static void testRightSkewed(S61_Mid_129_求根到叶子节点数字之和 solution) {
        TreeNode root = new TreeNode(9, null,
                new TreeNode(8, null,
                        new TreeNode(7)));
        int ans = solution.sumNumbers(root);
        System.out.println("测试6: 右链[9->8->7] 期望:987 实际:" + ans);
        assert ans == 987 : "右链路径数错误";
        System.out.println("路径: 987 -> 总和987 ✓\n");
    }

    // 包含 0 节点
    private static void testTreeWithZero(S61_Mid_129_求根到叶子节点数字之和 solution) {
        //      1
        //     / \
        //    0   2
        //     \
        //      3  -> 路径: 1->0->3 = 103, 1->2 = 12
        TreeNode root = new TreeNode(1,
                new TreeNode(0, null, new TreeNode(3)),
                new TreeNode(2));
        int ans = solution.sumNumbers(root);
        System.out.println("测试7: 包含0节点 期望:115 (103 + 12) 实际:" + ans);
        assert ans == 115 : "包含0节点路径数错误";
        System.out.println("路径: 103,12 -> 总和115 ✓\n");
    }

    // 递归 vs 迭代一致性
    private static void testConsistencyRecursiveIterative(S61_Mid_129_求根到叶子节点数字之和 solution) {
        TreeNode root = new TreeNode(2,
                new TreeNode(1, new TreeNode(4), new TreeNode(5)),
                new TreeNode(3, new TreeNode(6), new TreeNode(7)));
        int rec = solution.sumNumbers(root);
        int ite = solution.sumNumbersIterative(root);
        System.out.println("测试8: 递归vs迭代 一致性校验 期望相同 实际: rec=" + rec + ", ite=" + ite);
        assert rec == ite : "两种实现结果不一致";
        System.out.println("✓\n");
    }

    // 完全二叉树
    private static void testCompleteBinaryTree(S61_Mid_129_求根到叶子节点数字之和 solution) {
        TreeNode root = new TreeNode(1,
                new TreeNode(2, new TreeNode(4), new TreeNode(5)),
                new TreeNode(3, new TreeNode(6), new TreeNode(7)));
        int ans = solution.sumNumbers(root);
        System.out.println("测试9: 完全二叉树 期望:522 (124+125+136+137) 实际:" + ans);
        assert ans == 522 : "完全二叉树路径数错误";
        System.out.println("路径: 124,125,136,137 -> 总和522 ✓\n");
    }

    // 较大一些的自定义树
    private static void testLargerTree(S61_Mid_129_求根到叶子节点数字之和 solution) {
        TreeNode root = new TreeNode(5,
                new TreeNode(1,
                        new TreeNode(0),
                        new TreeNode(3, new TreeNode(8), null)),
                new TreeNode(9,
                        new TreeNode(4),
                        new TreeNode(2, null, new TreeNode(7))));
        int ansRec = solution.sumNumbers(root);
        int ansIte = solution.sumNumbersIterative(root);
        System.out.println("测试10: 较大树 期望:12169 实际:递归=" + ansRec + ", 迭代=" + ansIte);
        assert ansRec == 12169 : "较大树递归结果错误";
        assert ansIte == 12169 : "较大树迭代结果错误";
        System.out.println("路径: 510,5138,594,5927 -> 总和12169 ✓\n");
    }

    // 随机生成若干小规模树做一致性验证
    private static void testRandomSmallTrees(S61_Mid_129_求根到叶子节点数字之和 solution) {
        java.util.Random rand = new java.util.Random(42);
        for (int t = 1; t <= 5; t++) {
            TreeNode root = generateRandomTree(rand, 0, 4); // 深度<=4
            int rec = solution.sumNumbers(root);
            int ite = solution.sumNumbersIterative(root);
            assert rec == ite : "随机树结果不一致";
        }
        System.out.println("测试11: 随机小树递归与迭代一致性 ✓\n");
    }

    // 生成随机树（为防止节点过多，限制最大深度；节点值 0-9）
    private static TreeNode generateRandomTree(java.util.Random rand, int depth, int maxDepth) {
        if (depth > maxDepth) return null;
        // 随机决定是否生成节点（根必须生成，之后有概率为空）
        if (depth != 0 && rand.nextDouble() < 0.3) {
            return null;
        }
        TreeNode node = new TreeNode(rand.nextInt(10));
        node.left = generateRandomTree(rand, depth + 1, maxDepth);
        node.right = generateRandomTree(rand, depth + 1, maxDepth);
        return node;
    }
}
